import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * 手写动态数组
 */
public class DynamicArray<E> {

    // 真正存储数据的底层数组
    private E[] data;
    // 记录当前元素个数
    private int size;
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    public DynamicArray() {
        this(DEFAULT_CAPACITY);
    }

    public DynamicArray(int initCapacity) {
        // 数组扩容或缩容
        data = (E[]) new Object[initCapacity];
        size = 0;
    }

    // 增
    public void addLast(E e) {
        int cap = data.length;
        // 检查数组是否已满
        if (size == cap) {
            resize(cap * 2);
        }

    //     在尾部插入元素
        data[size] = e;
        size++;
    }

    public void add(int index, E e) {
        // 检查索引是否越界
        checkPositionIndex(index);
        int cap = data.length;
        if (size == cap) {
            resize(cap * 2);
        }
        // 搬迁数据 data[index] -> data[index + 1]
        // 给新元素腾出位置
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        // 插入新元素
        data[index] = e;
        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public E removeLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        int cap = data.length;
        if (size == cap / 4 && cap / 2 != 0) {
            // 缩容
            resize(cap / 2);
        }
        E deleteVal =  data[size - 1];
        // 删除最后一个元素
        // 必须给最后一个元素置为null，否则会造成内存泄露
        data[size - 1] = null;
        size--;
        return deleteVal;
    }

    public E remove(int index) {
        // 检查索引是否越界
        checkElementIndex(index);
        int cap = data.length;
        if (size == cap / 4 && cap / 2 != 0) {
            resize(cap / 2);
        }
        E deleteVal = data[index];
        // 搬移数据 data[index] -> data[index - 1]
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        data[size - 1] = null;
        return deleteVal;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E get(int index) {
        // 检查索引是否越界
        checkElementIndex(index);
        return data[index];
    }

    public E set(int index, E e) {
        // 检查索引越界
        checkElementIndex(index);
        // 修改数据
        E oldVal = data[index];
        data[index] = e;
        return oldVal;
    }

    // 工具方法
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    // 检查index索引位置是否可以存在元素
    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    /**
     * 检查index索引位置是否可以插入元素
     * @param index
     */
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }

    private void display() {
        System.out.println("size: " + size + '\t' + "cap = " + data.length);
        System.out.println(Arrays.toString(data));
    }

    // 将data容量改为newCap
    private void resize(int newCap) {
        E[] temp = (E[]) new Object[newCap];

        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }

        data = temp;
    }

    public static void main(String[] args) {
        // 初始容量设置为3
        DynamicArray<Integer> dynamicArray = new DynamicArray<>(3);
        // 添加5个元素
        for (int i = 0; i < 5; i++) {
            dynamicArray.addLast(i);
        }

        dynamicArray.remove(1);
        dynamicArray.add(1,999);
        dynamicArray.set(3, 9999);
        dynamicArray.get(3);
        Integer i = dynamicArray.removeLast();
        dynamicArray.display();

    }
}
